home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / bool_lib / adjacncy.c next >
Encoding:
C/C++ Source or Header  |  1994-09-07  |  27.2 KB  |  637 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d (not only polygonal) solid modeller.             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *  Module to handle adjacancies between polygons. Each edge has exactly two  *
  7. * polygons which share it. An edge is implicitly defined by the VList - each *
  8. * IPVertexStruct defines an edge with its succesor, and has a pointer to the *
  9. * other polygons using that edge. Those pointers are our target in this      *
  10. * module.                                     *
  11. *****************************************************************************/
  12.  
  13. #include <stdio.h>
  14. #include <math.h>
  15. #include "irit_sm.h"
  16. #include "allocate.h"
  17. #include "bool_loc.h"
  18.  
  19. /* #define DEBUG1         If the adjacencies should be printed to stdout. */
  20. /* #define DEBUG2     If the hash table content should be printed to stdout. */
  21.  
  22. #define HASH_TABLE_SIZE  100
  23. #define HASH_TABLE_SIZE1 101                 /* One above the above. */
  24. #define HASH_TABLE_SIZE2 50                   /* Half of the above. */
  25.  
  26. typedef struct HashTableEntry {
  27.     int Key;
  28.     IPPolygonStruct *Pl;
  29.     IPVertexStruct *V;
  30.     struct HashTableEntry *Pnext;
  31. } HashTableEntry;
  32.  
  33. typedef struct HashTableStruct {
  34.     HashTableEntry *Entry[HASH_TABLE_SIZE1];
  35. } HashTableStruct;
  36.  
  37. /* Prototypes of local function of adjacecies module: */
  38. static void InsertHashTable(HashTableStruct *HashTbl,
  39.                 IPPolygonStruct *Pl,
  40.                 IPVertexStruct *V);
  41. static int EdgeKey(IPVertexStruct *V);
  42. static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl,
  43.                      int EntryNum,
  44.                      HashTableEntry *PHash);
  45. static int SameEdges(PointType V1E1,
  46.              PointType V2E1,
  47.              PointType V1E2,
  48.              PointType V2E2);
  49. static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
  50.                   HashTableEntry *PHash);
  51. static void SecondEdgeKey(IPVertexStruct *V, int *Key1, int *Key2);
  52. static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
  53.                        int EntryNum,
  54.                        HashTableEntry *PHash);
  55. static int TestSameDir(PointType Pt11,
  56.                PointType Pt12,
  57.                PointType Pt21,
  58.                PointType Pt22);
  59. static void DeleteHashTable(HashTableStruct *SecondHashTable,
  60.                 IPVertexStruct *V,
  61.                 int EntryNum);
  62.  
  63. /*****************************************************************************
  64. * DESCRIPTION:                                                               M
  65. *   Routine to generate adjacencies to the given object.                     M
  66. *   Note an edge might be only partially adjacent to another edge, and a     M
  67. * second attempt is made to find (again only part of - see below) them. Any  M
  68. * case, FALSE will be returned as there is no way we can say the object is   M
  69. * perfectly closed!                                 M
  70. *   This is the only routine to generate the adjacencies of a geometric      M
  71. * object. These adjacencies are needed for the boolean operations on them.   M
  72. *   Algorithm: for each edge, for each polygon in the object, the edges are  M
  73. * sorted according to the key defined by EdgeKey routine (sort in hash tbl). M
  74. * A second path on the table is made to match common keys edges and set the  M
  75. * pointers from one to another. Note that each edge is common to exactly 2   M
  76. * faces if it is internal, or exactly 1 face if it is on the border (if the  M
  77. * object is open).                                 M
  78. *                                                                            *
  79. * PARAMETERS:                                                                M
  80. *   PObj: The polygonal object to compute the adjacency information for.     M
  81. *                                                                            *
  82. * RETURN VALUE:                                                              M
  83. *   int: TRUE if all adjacencies were resolved, or the object is completely  M
  84. *        closed.                                                             M
  85. *                                                                            *
  86. * KEYWORDS:                                                                  M
  87. *   BoolGenAdjacencies, adjacency, topology                                  M
  88. *****************************************************************************/
  89. int BoolGenAdjacencies(IPObjectStruct *PObj)
  90. {
  91.     int i, IsOpenObject;
  92.     HashTableStruct *HashTbl, *SecondHashTbl;
  93.     HashTableEntry *PHash, *PHashMatch;
  94.     IPPolygonStruct *Pl;
  95.     IPVertexStruct *V;
  96.  
  97.     if (!IP_IS_POLY_OBJ(PObj))
  98.     IritFatalError("GenAdjacencies: Non polygonal object");
  99.     if (IP_IS_POLYLINE_OBJ(PObj))
  100.     return TRUE;                 /* No adj. in polyline obj. */
  101.  
  102.     IsOpenObject = FALSE;            /* "Default" is closed object... */
  103.  
  104.     /* Prepare hash tables (for first and second attempts) and clear them.   */
  105.     HashTbl = (HashTableStruct *) IritMalloc(sizeof(HashTableStruct));
  106.     for (i = 0; i < HASH_TABLE_SIZE1; i++)
  107.     HashTbl -> Entry[i] = NULL;
  108.     SecondHashTbl = (HashTableStruct *) IritMalloc(sizeof(HashTableStruct));
  109.     for (i = 0; i < HASH_TABLE_SIZE1; i++)
  110.     SecondHashTbl -> Entry[i] = NULL;
  111.  
  112.     /* Step one - enter all the edges into the hash table: */
  113.     Pl = PObj -> U.Pl;
  114.     while (Pl) {
  115.     V = Pl -> PVertex;
  116.     do {
  117.         InsertHashTable(HashTbl, Pl, V); /* Insert the edge V..V->Pnext. */
  118.         V = V -> Pnext;
  119.     } while (V != NULL && V != Pl -> PVertex);
  120.     Pl = Pl -> Pnext;
  121.     }
  122.  
  123. #ifdef DEBUG2
  124.     printf("Hash Table content:\n");
  125.     for (i = 0; i < HASH_TABLE_SIZE; i++) {
  126.     PHash = HashTbl -> Entry[i];
  127.     if (PHash)
  128.         printf("\nHashTable entry %d:\n", i);
  129.     while (PHash) {
  130.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  131.         PHash -> V -> Coord[0],
  132.         PHash -> V -> Coord[1],
  133.         PHash -> V -> Coord[2],
  134.         PHash -> V -> Pnext -> Coord[0],
  135.         PHash -> V -> Pnext -> Coord[1],
  136.         PHash -> V -> Pnext -> Coord[2]);
  137.         PHash = PHash -> Pnext;
  138.     }
  139.     }
  140. #endif /* DEBUG2 */
  141.  
  142.     /* Step two - scans all the entries and look for the matching edge.      */
  143.     for (i = 0; i < HASH_TABLE_SIZE; i++)
  144.     while (HashTbl -> Entry[i] != NULL) {
  145.         PHash = HashTbl -> Entry[i]; /* Remove one edge from hash table. */
  146.         HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;
  147.  
  148.         /* Find matching edge (if perfect match - exactly the same edge) */
  149.         /* Otherwise put the edge in SecondHashTbl.                 */
  150.         if ((PHashMatch = FindMatchEdge(HashTbl, i, PHash)) == NULL) {
  151.         PHash -> V -> PAdj = NULL;
  152.         InsertSecondHashTable(SecondHashTbl, PHash);
  153.         IsOpenObject = TRUE;
  154.         }
  155.         else {
  156. #        ifdef DEBUG1
  157.             /* If DEBUG1 switch the pointers of the edges themselves.*/
  158.             PHash -> V -> PAdj = (IPPolygonStruct *) PHashMatch -> V;
  159.             PHashMatch -> V -> PAdj = (IPPolygonStruct *) PHash -> V;
  160. #        else
  161.             /* Otherwise switch pointers of the edges polygons */
  162.             PHash -> V -> PAdj = PHashMatch -> Pl;
  163.             PHashMatch -> V -> PAdj = PHash -> Pl;
  164. #        endif /* DEBUG1 */
  165.  
  166.         IritFree((VoidPtr) PHash);
  167.         IritFree((VoidPtr) PHashMatch);
  168.         }
  169.     }
  170.  
  171. #ifdef DEBUG1
  172.     printf("Adjacencies for object %s (found to be open = %d)\n",
  173.     PObj -> Name, IsOpenObject);
  174.     Pl = PObj -> U.Pl.P;
  175.     /* Note that adjacency in DEBUG1 is the other edge, not other polygon. */
  176.     while (Pl) {
  177.     V = Pl -> V;
  178.     do {
  179.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  180.         V -> Coord[0], V -> Coord[1], V -> Coord[2],
  181.         V -> Pnext -> Coord[0], V -> Pnext -> Coord[1],
  182.         V -> Pnext -> Coord[2]);
  183.         if (V -> PAdj != NULL)
  184.         printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
  185.             ((IPVertexStruct *) V -> PAdj) -> Coord[0],
  186.             ((IPVertexStruct *) V -> PAdj) -> Coord[1],
  187.             ((IPVertexStruct *) V -> PAdj) -> Coord[2],
  188.             ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[0],
  189.             ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[1],
  190.             ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[2]);
  191.         else
  192.         printf("No Match!\n\n");
  193.         V = V -> Pnext;
  194.     } while (V != NULL && V != Pl -> V);
  195.     Pl = Pl -> Pnext;
  196.     }
  197. #endif /* DEBUG1 */
  198.  
  199. #ifdef DEBUG2
  200.     printf("Hash Table content left after all full matches were deleted:\n");
  201.     for (i = 0; i < HASH_TABLE_SIZE; i++) {
  202.     PHash = SecondHashTbl -> Entry[i];
  203.     if (PHash)
  204.         printf("\nHashTable entry %d:\n", i);
  205.     while (PHash) {
  206.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  207.         PHash -> V -> Coord[0],
  208.         PHash -> V -> Coord[1],
  209.         PHash -> V -> Coord[2],
  210.         PHash -> V -> Pnext -> Coord[0],
  211.         PHash -> V -> Pnext -> Coord[1],
  212.         PHash -> V -> Pnext -> Coord[2]);
  213.         PHash = PHash -> Pnext;
  214.     }
  215.     }
  216. #endif /* DEBUG2 */
  217.  
  218.     /* Time to activate the second attempt - scan SecondHashTable for edges  */
  219.     /* partially adjacent to each other, but with one common vertex!         */
  220.     for (i = 0; i < HASH_TABLE_SIZE; i++)
  221.     while (SecondHashTbl -> Entry[i] != NULL) {
  222.         PHash = SecondHashTbl -> Entry[i];/* Remove one edge from table. */
  223.         SecondHashTbl -> Entry[i] = SecondHashTbl -> Entry[i] -> Pnext;
  224.  
  225.         /* Remove the second instance of this edge with other key: */
  226.         DeleteHashTable(SecondHashTbl, PHash -> V, PHash -> Key);
  227.  
  228.         /* Find matching edge (if perfect match - exactly the same edge) */
  229.         /* Otherwise put the edge in SecondHashTbl.                 */
  230.         if ((PHashMatch = FindSecondMatchEdge(SecondHashTbl, i, PHash)) ==
  231.                                     NULL) {
  232.         PHash -> V -> PAdj = NULL;            /* Failed again! */
  233.         IritFree((VoidPtr) PHash);
  234.         }
  235.         else {
  236. #        ifdef DEBUG1
  237.             /* If DEBUG1 switch the pointers of the edges themselves. */
  238.             PHash -> V -> PAdj = (IPPolygonStruct *) PHashMatch -> V;
  239.             PHashMatch -> V -> PAdj = (IPPolygonStruct *) PHash -> V;
  240. #        else
  241.             /* Otherwise switch pointers of the edges polygons. */
  242.             PHash -> V -> PAdj = PHashMatch -> Pl;
  243.             PHashMatch -> V -> PAdj = PHash -> Pl;
  244. #        endif /* DEBUG1 */
  245.  
  246.         IritFree((VoidPtr) PHash);
  247.         IritFree((VoidPtr) PHashMatch);
  248.         }
  249.     }
  250.  
  251. #ifdef DEBUG1
  252.     printf("Adjacencies for object %s - second attempt (found to be open = %d)\n",
  253.     PObj -> Name, IsOpenObject);
  254.     Pl = PObj -> U.Pl.P;
  255.     /* Note that adjacency in DEBUG1 is the other edge, not other polygon. */
  256.     while (Pl) {
  257.     V = Pl -> V;
  258.     do {
  259.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  260.         V -> Coord[0], V -> Coord[1], V -> Coord[2],
  261.         V -> Pnext -> Coord[0], V -> Pnext -> Coord[1],
  262.         V -> Pnext -> Coord[2]);
  263.         if (V -> PAdj != NULL)
  264.         printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
  265.             ((IPVertexStruct *) V -> PAdj) -> Coord[0],
  266.             ((IPVertexStruct *) V -> PAdj) -> Coord[1],
  267.             ((IPVertexStruct *) V -> PAdj) -> Coord[2],
  268.             ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[0],
  269.             ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[1],
  270.             ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[2]);
  271.         else
  272.         printf("No Match!\n\n");
  273.         V = V -> Pnext;
  274.     } while (V != NULL && V != Pl -> V);
  275.     Pl = Pl -> Pnext;
  276.     }
  277. #endif /* DEBUG1 */
  278.  
  279.     IritFree((VoidPtr) HashTbl);
  280.     IritFree((VoidPtr) SecondHashTbl);
  281.  
  282.     return !IsOpenObject;
  283. }
  284.  
  285. /*****************************************************************************
  286. * DESCRIPTION:                                                               *
  287. *   Evaluates a key (integer!) from the given vertex V (in polygon Pl) and   *
  288. * insert that in the hash table:                         *
  289. *                                                                            *
  290. * PARAMETERS:                                                                *
  291. *   HashTbl:  To be used.                                                    *
  292. *   Pl:       Polygon containing vertex.                                     *
  293. *   V:        Vertex to insert into hash table.                              *
  294. *                                                                            *
  295. * RETURN VALUE:                                                              *
  296. *   void                                                                     *
  297. *****************************************************************************/
  298. static void InsertHashTable(HashTableStruct *HashTbl,
  299.                 IPPolygonStruct *Pl,
  300.                 IPVertexStruct *V)
  301. {
  302.     int Key;
  303.     HashTableEntry *PHash;
  304.  
  305.     PHash = (HashTableEntry *) IritMalloc(sizeof(HashTableEntry));
  306.     PHash -> Pl = Pl;
  307.     PHash -> V = V;
  308.     PHash -> Key = Key = EdgeKey(V);
  309.     PHash -> Pnext = HashTbl -> Entry[Key];
  310.     HashTbl -> Entry[Key] = PHash;
  311. }
  312.  
  313. /*****************************************************************************
  314. * DESCRIPTION:                                                               *
  315. *   This routine evaluates a key for a given edge. In order the try to make  *
  316. * them unique as possible, the point is projected on a "random" vector. I    *
  317. * picked vector X + 1.57 * Y + 1.29 * Z. If you have better one - change it. *
  318. *   The key itself is the average of the two vertices keys.             *
  319. *   Note we get best results if the object is between ~-10..10.             *
  320. *                                                                            *
  321. * PARAMETERS:                                                                *
  322. *   V:   To computed key for.                                                *
  323. *                                                                            *
  324. * RETURN VALUE:                                                              *
  325. *   int: The resulting key.                                                  *
  326. *****************************************************************************/
  327. static int EdgeKey(IPVertexStruct *V)
  328. {
  329.     int key;
  330.     RealType RKey1, RKey2;
  331.  
  332.     RKey1 = (V -> Coord[0] + 1.57 * V -> Coord[1] + 1.29 * V -> Coord[2]);
  333.     V = V -> Pnext;
  334.     RKey2 = (V -> Coord[0] + 1.57 * V -> Coord[1] + 1.29 * V -> Coord[2]);
  335.  
  336.     key = (((int) ((RKey1 + RKey2) * 10.0)) + HASH_TABLE_SIZE) / 2;
  337.  
  338.     return BOUND(key, 0, HASH_TABLE_SIZE - 1);
  339. }
  340.  
  341. /*****************************************************************************
  342. * DESCRIPTION:                                                               *
  343. *   Searches the hash table for matching with a given edge pointed by PHash. *
  344. * PHash was extracted from the hash table in entry EntryNum, so the match    *
  345. * is probably in the same entry. If it is not, it must be (if there is one!) *
  346. * in EntryNum+1 as we scans the entries in order and (EntryNum-1) is empty.  *
  347. *   Note that idealy the match was in EntryNum, but because of real number   *
  348. * errors there is a small chance it will be in its neibours: EntryNum +/- 1. *
  349. *                                                                            *
  350. * PARAMETERS:                                                                *
  351. *   HashTbl:   To search.                                                    *
  352. *   EntryNum:  The probably contains the matching to PHash.                  *
  353. *   PHash:     To find a match for.                                          *
  354. *                                                                            *
  355. * RETURN VALUE:                                                              *
  356. *   HashTableEntry *:  The matched entry.                                    *
  357. *****************************************************************************/
  358. static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl,
  359.                      int EntryNum,
  360.                      HashTableEntry *PHash)
  361. {
  362.     int i;
  363.     HashTableEntry *PMatch,
  364.     *PLast = NULL;
  365.  
  366.     for (i = EntryNum; i <= EntryNum+1; i++) {
  367.     PMatch = HashTbl -> Entry[i];
  368.     while (PMatch) {
  369.         if (SameEdges(PHash -> V -> Coord,  PHash -> V -> Pnext -> Coord,
  370.               PMatch -> V -> Coord, PMatch -> V -> Pnext -> Coord)) {
  371.         /* Delete the matched edge from hash table, and return it: */
  372.         if (PMatch == HashTbl -> Entry[i])
  373.             HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;
  374.         else
  375.             PLast -> Pnext = PLast -> Pnext -> Pnext;
  376.         return PMatch;
  377.         }
  378.         PLast = PMatch;
  379.         PMatch = PMatch -> Pnext;
  380.     }
  381.     }
  382.  
  383.     return NULL;                  /* No match for this one ! */
  384. }
  385.  
  386. /*****************************************************************************
  387. * DESCRIPTION:                                                               *
  388. *   Compere two edges - if the same up to BOOL_EPSILON (see BOOL_PT_APX_EQ). *
  389. * The two vetrices of each edge are given, but no order on them is assumed   *
  390. *                                                                            *
  391. * PARAMETERS:                                                                *
  392. *   V1E1, V2E1: Two vertices of first edge.                                  *
  393. *   V1E2, V2E2: Two vertices of second edge.                                 *
  394. *                                                                            *
  395. * RETURN VALUE:                                                              *
  396. *   inr: TRUE is found the same, FALSE otherwise.                            *
  397. *****************************************************************************/
  398. static int SameEdges(PointType V1E1,
  399.              PointType V2E1,
  400.              PointType V1E2,
  401.              PointType V2E2)
  402. {
  403.     return (BOOL_PT_APX_EQ(V1E1, V1E2) && BOOL_PT_APX_EQ(V2E1, V2E2)) ||
  404.        (BOOL_PT_APX_EQ(V1E1, V2E2) && BOOL_PT_APX_EQ(V2E1, V1E2));
  405. }
  406.  
  407. /*****************************************************************************
  408. *   Everything from this point handles the second attempt - match edges      *
  409. * which are not complete match - cases which one edge is only part of its    *
  410. * adjacent one. We trap only cases which the two edges has common vertex. If *
  411. * the two edges has no common vertex (i.e. one is totally in the other) we   *
  412. * still misses that. You are invited to improve that. Any case this one will *
  413. * have influence in extremely rare cases (The booleans will usually          *
  414. * propagate the information using the common vertex edges).                 *
  415. *   Note, the obvious, that if one edge is adjacent to few edges, only one   *
  416. * (arbitrarily) will result in the match, and the other will result as NULL. *
  417. *****************************************************************************/
  418.  
  419. /*****************************************************************************
  420. * DESCRIPTION:                                                               *
  421. *   Evaluates two keys (integer!) from a given edge in HashTableEntry.       *
  422. *   This time keys are of the vertices themselves (see SecondEdgeKet rtn).   *
  423. *   Note each HashTableEntry hold the key of the other entry this time...    *
  424. *                                                                            *
  425. * PARAMETERS:                                                                *
  426. *   SecondHashTbl:   See above.                                               *
  427. *   PHash:           See above.                                              *
  428. *                                                                            *
  429. * RETURN VALUE:                                                              *
  430. *   void                                                                     *
  431. *****************************************************************************/
  432. static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
  433.                   HashTableEntry *PHash)
  434. {
  435.     int Key1, Key2;
  436.     HashTableEntry *PHash2;
  437.  
  438.     SecondEdgeKey(PHash -> V, &Key1, &Key2);
  439.  
  440.     /* And insert the edge as at Key1 (using given HashTableEntry PHash): */
  441.     PHash -> Key = Key2;
  442.     PHash -> Pnext = SecondHashTbl -> Entry[Key1];
  443.     SecondHashTbl -> Entry[Key1] = PHash;
  444.  
  445.     /* And insert the edge as at Key2 (allocating new HashTableEntry for it):*/
  446.     PHash2 = (HashTableEntry *) IritMalloc(sizeof(HashTableEntry));
  447.     PHash2 -> Pl = PHash -> Pl;
  448.     PHash2 -> V = PHash -> V;
  449.     PHash2 -> Key = Key1;
  450.     PHash2 -> Pnext = SecondHashTbl -> Entry[Key2];
  451.     SecondHashTbl -> Entry[Key2] = PHash2;
  452. }
  453.  
  454. /*****************************************************************************
  455. * DESCRIPTION:                                                               *
  456. *   This routine evaluates two keys for the given edge - one for each of its *
  457. * vertices, and again tries to make them unique as passible:             *
  458. * picked the same vector: X + 1.57 * Y + 1.29 * Z.                 *
  459. *   Note we get best results if the object is between ~-10..10.             *
  460. *                                                                            *
  461. * PARAMETERS:                                                                *
  462. *   V:        To compute keys for it and its next vertex, forming the edge.  *
  463. *   Key1, Key2: The resulting two keys of the two vertices.                  *
  464. *                                                                            *
  465. * RETURN VALUE:                                                              *
  466. *   void                                                                     *
  467. *****************************************************************************/
  468. static void SecondEdgeKey(IPVertexStruct *V, int *Key1, int *Key2)
  469. {
  470.     RealType RKey;
  471.  
  472.     RKey = (V -> Coord[0] + 1.57 * V -> Coord[1] + 1.29 * V -> Coord[2]);
  473.     *Key1 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
  474.     *Key1 = BOUND(*Key1, 0, HASH_TABLE_SIZE - 1);
  475.  
  476.     V = V -> Pnext;
  477.     RKey = (V -> Coord[0] + 1.57 * V -> Coord[1] + 1.29 * V -> Coord[2]);
  478.     *Key2 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
  479.     *Key2 = BOUND(*Key2, 0, HASH_TABLE_SIZE - 1);
  480. }
  481.  
  482. /*****************************************************************************
  483. * DESCRIPTION:                                                               *
  484. *   Search The hash table for matching with the given edge pointed by PHash, *
  485. * as in the second attempt: the keys used here are of the vertices         *
  486. * themselves, so we should search for match in given index EntryNum only.    *
  487. * We search for same vertex AND same direction, which if both match, confirm *
  488. * at list partial adjacency between the two edges (both with same vertex as  *
  489. * one end - the vertex with this key).                         *
  490. *                                                                            *
  491. * PARAMETERS:                                                                *
  492. *   SecondHashTbl:    Containing the edge database.                          *
  493. *   EntryNum:         Where to look at the database.                         *
  494. *   PHash:            To search for a match                                  *
  495. *                                                                            *
  496. * RETURN VALUE:                                                              *
  497. *   HashTableEntry:   Found match, if any.                                   *
  498. *****************************************************************************/
  499. static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
  500.                        int EntryNum,
  501.                        HashTableEntry *PHash)
  502. {
  503.     int EqualFirst,
  504.     SameDir = FALSE;
  505.     HashTableEntry *PMatch,
  506.     *PLast = NULL;
  507.  
  508.     PMatch = SecondHashTbl -> Entry[EntryNum]; /* It must be here if exists. */
  509.     while (PMatch) {
  510.     if ((EqualFirst = BOOL_PT_APX_EQ(PHash -> V -> Coord,
  511.                      PMatch -> V -> Coord)) != 0 ||
  512.         BOOL_PT_APX_EQ(PHash -> V -> Coord,
  513.                PMatch -> V -> Pnext -> Coord)) {
  514.         /* Found same vertex in PMatch as first vertex in PHash - test   */
  515.         /* the direction vectors, to be same also:                 */
  516.         if (EqualFirst) {
  517.         SameDir = TestSameDir(PHash -> V -> Pnext -> Coord,
  518.                       PHash -> V -> Coord,
  519.                       PMatch -> V -> Pnext -> Coord,
  520.                       PMatch -> V -> Coord);
  521.         }
  522.         else {
  523.         SameDir = TestSameDir(PHash -> V -> Pnext -> Coord,
  524.                       PHash -> V -> Coord,
  525.                       PMatch -> V -> Coord,
  526.                       PMatch -> V -> Pnext -> Coord);
  527.         }
  528.     }
  529.     else if ((EqualFirst = BOOL_PT_APX_EQ(PHash -> V -> Pnext -> Coord,
  530.                           PMatch -> V -> Coord)) != 0 ||
  531.         BOOL_PT_APX_EQ(PHash -> V -> Pnext -> Coord,
  532.                PMatch -> V -> Pnext -> Coord)) {
  533.         /* Found same vertex in PMatch as second vertex in PHash - test  */
  534.         /* the direction vectors, to be same also:                 */
  535.         if (EqualFirst) {
  536.         SameDir = TestSameDir(PHash -> V -> Coord,
  537.                       PHash -> V -> Pnext -> Coord,
  538.                       PMatch -> V -> Pnext -> Coord,
  539.                       PMatch -> V -> Coord);
  540.         }
  541.         else {
  542.         SameDir = TestSameDir(PHash -> V -> Coord,
  543.                       PHash -> V -> Pnext -> Coord,
  544.                       PMatch -> V -> Coord,
  545.                       PMatch -> V -> Pnext -> Coord);
  546.         }
  547.     }
  548.  
  549.     if (SameDir) {           /* TRUE iff same vertex AND same direction!!! */
  550.         /* Delete the matched edge from the hash table, its compliment   */
  551.         /* with the second key and return a pointer to it:             */
  552.         if (PMatch == SecondHashTbl -> Entry[EntryNum])
  553.         SecondHashTbl -> Entry[EntryNum] =
  554.             SecondHashTbl -> Entry[EntryNum] -> Pnext;
  555.         else
  556.         PLast -> Pnext = PLast -> Pnext -> Pnext;
  557.         /* Uses the key in structure (hold key of other entry!): */
  558.         DeleteHashTable(SecondHashTbl, PMatch -> V, PMatch -> Key);
  559.         return PMatch;
  560.     }
  561.     PLast = PMatch;
  562.     PMatch = PMatch -> Pnext;
  563.     }
  564.  
  565.     return NULL; /* No match for this one ! */
  566. }
  567.  
  568. /*****************************************************************************
  569. * DESCRIPTION:                                                               *
  570. *   Test if the two points pairs (defining two edges) are actually on the    *
  571. * same direction - find normalized direction vector for each and test if     *
  572. * their dot product is equal to 1.                         *
  573. *                                                                            *
  574. * PARAMETERS:                                                                *
  575. *   Pt11, Pt12:  The pair defining the first line.                           *
  576. *   Pt21, Pt22:  The pair defining the second line.                          *
  577. *                                                                            *
  578. * RETURN VALUE:                                                              *
  579. *   int:   TRUE if same direction, FALSE otherwise.                          *
  580. *****************************************************************************/
  581. static int TestSameDir(PointType Pt11,
  582.                PointType Pt12,
  583.                PointType Pt21,
  584.                PointType Pt22)
  585. {
  586.     PointType Dir1, Dir2;
  587.  
  588.     PT_SUB(Dir1, Pt12, Pt11);
  589.     PT_SUB(Dir2, Pt22, Pt21);
  590.  
  591.     PT_NORMALIZE(Dir1);
  592.     PT_NORMALIZE(Dir2);
  593.  
  594.     return BOOL_APX_EQ(DOT_PROD(Dir1, Dir2), 1.0);
  595. }
  596.  
  597. /*****************************************************************************
  598. * DESCRIPTION:                                                               *
  599. *   Delete entry in SecondHashTable index EntryNum, which holds vertex V.    *
  600. * This vertex MUST be there, otherwise its a fatal error.             *
  601. *                                                                            *
  602. * PARAMETERS:                                                                *
  603. *   SecondHashTable:    Data base.                                           *
  604. *   V:                  Vertex to be removed from data base.                 *
  605. *   EntryNum:           Where to search for V in data base.                  *
  606. *                                                                            *
  607. * RETURN VALUE:                                                              *
  608. *   void                                                                     *
  609. *****************************************************************************/
  610. static void DeleteHashTable(HashTableStruct *SecondHashTable,
  611.                 IPVertexStruct *V,
  612.                 int EntryNum)
  613. {
  614.     HashTableEntry
  615.     *PLast = NULL,
  616.     *PHash = SecondHashTable -> Entry[EntryNum];
  617.  
  618.     while (PHash != NULL) {
  619.     if (PHash -> V == V)
  620.         break;
  621.     PLast = PHash;
  622.     PHash = PHash -> Pnext;
  623.     }
  624.  
  625.     if (PHash == NULL)
  626.     IritFatalError("DeleteHashTable: No hash table entry to delete");
  627.     else {
  628.     if (PHash == SecondHashTable -> Entry[EntryNum])
  629.         SecondHashTable -> Entry[EntryNum] =
  630.         SecondHashTable -> Entry[EntryNum] -> Pnext;
  631.     else
  632.         PLast -> Pnext = PHash -> Pnext;
  633.     IritFree((VoidPtr) PHash);
  634.     }
  635. }
  636.  
  637.